package suanfa;

import org.junit.Test;

/**
 * 正则表达式匹配
 * 给定一个字符串(s)和一个字符模式（p），实现支持'.'和'*'的正则表达式匹配
 * '.'匹配任意单个字符
 * '*'匹配零个或多个前面的元素
 * 匹配应该是覆盖整个字符串(s)，而不是部分字符串
 */
public class RegSolution
{


    enum Result {
        TRUE, FALSE
    }
    Result[][] memo;
    /**
     * 正则表达式匹配，这个没有看懂
     *
     * @param text 传入需要匹配的字符串
     * @param pattern 传入的规则
     * @return 结果
     */
    public boolean isMatch(String text, String pattern) {
        memo = new Result[text.length() + 1][pattern.length() + 1];
        return dp(0, 0, text, pattern);
    }

    public boolean dp(int i, int j, String text, String pattern) {
        if (memo[i][j] != null) {
            return memo[i][j] == Result.TRUE;
        }
        boolean ans;
        if (j == pattern.length()){
            ans = i == text.length();
        } else{
            boolean first_match = (i < text.length() &&
                    (pattern.charAt(j) == text.charAt(i) ||
                            pattern.charAt(j) == '.'));

            if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                ans = (dp(i, j+2, text, pattern) ||
                        first_match && dp(i+1, j, text, pattern));
            } else {
                ans = first_match && dp(i+1, j+1, text, pattern);
            }
        }
        memo[i][j] = ans ? Result.TRUE : Result.FALSE;
        return ans;
    }

    @Test
    public void test()
    {
        System.out.println(isMatch("aacsdc","a"));
    }
}



















